Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра СКС Звіт з лабораторної роботи № 3 з дисципліни: “Дискретна матетематика”  Львів 2013 Мета: навчитися створювати програму яка обчислює задачу про кістякове дерево екстремальної (мінімальної або максимальної) ваги Теоретичні відомості Діяльність сучасного суспільства тісно пов’язана з різного роду сітками – наприклад, транспорт, комунікації, розподіл товарів і т. д. математичний аналіз таких сіток став предметом фундаментальної важливості. В даній лабораторній роботі на прикладах показано, що аналіз сіток по суті еквівалентний вивченню орфографії. Завод електричних масажних щіток хотів би надіслати на даний ринок декілька ящиків своєї продукції. Припустимо, що ці ящики можна послати по декількох різних каналах, показаних на рис. 1, де
– завод,
– ринок., а числа означають максимальне число ящиків, що може бути надіслано по цій сітці, не перевищуючи допустиму пропускну здатність кожного каналу. Рис. 1 Рисунок 1 може описувати і другі ситуації. Наприклад, якщо кожна дуга цього орграфа являє собою вулицю з одностороннім рухом, а відповідні числа означають максимально можливий потік транспорту (число машин в годину) по цій вулиці, то хотілось би знайти найбільше можливе число машин, які можуть проїхати із
за одну годину. Цей рисунок можна розглядати і як схему електричної сітки, і тоді задача полягає в знаходженні максимального струму, який можна пропустити по цій сітці при умові, що задані допустимі струми окремих приводів. ОСНОВНА ЗАДАЧА ТЕОРІЇ ТРАНСПОРТНИХ СІТОК Введемо основні поняття теорії. Означення 1.1. транспортна сітка
є сукупність двох об’єктів: Зв’язного графа
з властивостями: В графі відсутні петлі. В графі
існує одна і лише одна вершина така, що множина
. В графі
існує одна і лише одна вершина
, така, що множина
. Цілочисельною невід’ємною функцією
, заданою на множині Г дуг графа
. Вершина
називається входом сітки, вершина
– виходом. Значення функції
на дузі
називається пропускною здатністю дуги. Означення 1.2. Нехай
– множина дуг, що заходять в вершину
, а
множина дуг, що виходять в вершини
. Цілочисельна невід’ємна функція
, задана на множині Г дуг графа
, називається потоком, якщо вона задовольняє такі умови:





Означення 1.3. Величина

– називається величиною потоку
і позначається через
. Задача. На даній транспортній сітці
побудувати потік найбільшої величини. Перш ніж викласти алгоритм розв’язку задачі, введемо ще два терміни. Дуга
називається насиченою, якщо
, потік
називається повним, якщо кожен шлях від
до
містить хоча б одну насичену дугу. АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА ДЛЯ ЗНАХОДЖЕННЯ ПОТОКУНАЙБІЛЬШОЇ ВЕЛЕЧИНИ Розглянемо алгоритм Форда на прикладі графа зображеного на мал.1 .
Припустимо, у нас витік буде в 1 вузлі, а стік в 4 вузлі. Алгоритм можна розбити на три кроки: 1.Пошук довільного шляху з витоку до стоку. Якщо такого немає, то видаємо значення максимальної пропускної спроможності і алгоритм завершується. 2.Знаходження в обраному шляху ребра з мінімальною пропускною здатністю. Додаємо значення цього ребра до пропускної спроможності, яка на початку виконання алгоритму дорівнює 0. 3.Віднімання з усіх значень ребер шляху, значення мінімального ребра цього шляху. При цьому саме ребро звернутися в 0 і його вже не можна враховувати в подальшому. Далі продовжуємо з кроку 1. На початку у нас пропускна здатність дорівнює 0 (P = 0). Припустимо, ми знайшли шлях з витоку 1 в стік 4 через вершини 2 і 3, тобто весь шлях можна записати як (1-2-3-4). У цьому шляху мінімальне ребро з'єднує вершини 2 і 3, його значення 5, збільшуємо пропускну...